package com.jinan.algorithm.bag;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 155. 最小栈<a href="https://leetcode-cn.com/problems/min-stack/">...</a>
 * 难度：中等
 * tag: 栈，设计
 * description:
 * 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
 * 实现  MinStack 类：
 * 1. MinStack() 初始化栈对象。
 * 2. void push(int val) 将元素 val 推入栈中。
 * 3. void pop() 删除栈顶的元素。
 * 4. int top() 获取栈顶元素。
 * 5. int getMin() 检索栈中的最小元素。
 */
class MinStack {

    private Deque<int[]> stack = new ArrayDeque<>();
    public MinStack() {
        stack.offerLast(new int[]{0, Integer.MAX_VALUE});
    }
    
    public void push(int val) {
        stack.offerLast(new int[]{val, Math.min(val, getMin())});
    }
    
    public void pop() {
        stack.pollLast();
    }
    
    public int top() {
        return stack.peekLast()[0];
    }
    
    public int getMin() {
        return stack.peekLast()[1];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */